Branch-and-Bound-Verfahren


Branch-and-Bound-Verfahren
1. Begriff: Verfahren des  Operations Research, bei dem ein zu lösendes kombinatorisches Optimierungsproblem (endliche Anzahl unabhängiger Variablen mit diskretem Wertevorrat) keiner effektiven analytischen Behandlung zugänglich ist oder Enumerationsverfahren ( Entscheidungsbaumverfahren) wegen des Rechenaufwandes ausscheiden. Lässt sich das Problem durch n diskrete Variablen, die jeweils k mögliche Werte annehmen können formulieren, dann liegt eine Interpretation als qualitatives Entscheidungsproblem nahe.
- 2. Vorgehensweise: Das Lösungsverfahren verwendet das Prinzip der Aufteilung und Begrenzung des Lösungsraumes, um eine vollständige Enumeration zu vermeiden. Schritte: a) Branch (Verzweigung): Einer der Variablen wird ein bestimmter zulässiger Wert zugeordnet, wodurch ein neues Unterproblem entsteht, dessen Umfang um eine Variable geringer ist. Bei k möglichen Werten für die ausgewählte Variable entstehen so k „einfachere“ Unterprobleme. Es bleibt festzustellen, welches der Unterprobleme die optimale Lösung enthält.
- b) Bound (Schranke): Nach der Fixierung einer Variablen wird ermittelt, wie die Lösung für die restlichen Variablen günstigenfalls ausfallen kann. Hat man für alle möglichen Werte einer ausgewählten Variablen die Bounds ermittelt, so wählt man die Alternative mit dem günstigsten Bound, um zur nächsten Verzweigung weiterzugehen. Wird nach mehrmaligem Branching und Bounding eine zulässige Lösung erreicht, so können alle Fälle mit ungünstigeren Bounds gestrichen werden. Das Optimum ist erreicht, wenn keine günstigere zulässige Lösung mehr zu erwarten ist.
- Die Güte eines B.-a.-B.-V. hängt wesentlich von der Auswahl der Bounds ab. Diese Auswahl kann nur heuristisch erfolgen; es ist deshalb nicht möglich, über die Konvergenz des Algorithmus Aussagen zu machen.
- 3. Anwendung: Prinzipiell ist das Verfahren auf alle diskreten Probleme anwendbar, v.a. auf Zuordnungs- und Travelling-Salesman-Probleme.

Lexikon der Economics. 2013.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Branch-and-Bound-Verfahren — Branch and Bound Verfahren,   Entscheidungsbaumverfahren …   Universal-Lexikon

  • Branch-and-bound-Verfahren —   [ brɑːntʃənd baʊnd ; englisch], Operationsresearch: Entscheidungsbaumverfahren …   Universal-Lexikon

  • Branch and Bound — (Verzweigung und Schranke) ist eine im Bereich Operations Research häufig verwendete mathematische Methode, deren Ziel darin besteht, für ein gegebenes ganzzahliges Optimierungsproblem eine beste Lösung zu finden. Branch and Bound führt auf einen …   Deutsch Wikipedia

  • Branch and bound — (Verzweigung und Schranke) ist eine im Bereich Operations Research häufig verwendete mathematische Methode, deren Ziel darin besteht, für ein gegebenes ganzzahliges Optimierungsproblem eine beste Lösung zu finden. Branch and Bound führt auf einen …   Deutsch Wikipedia

  • Branch-and-Bound — (Verzweigung und Schranke) ist eine im Bereich Operations Research häufig verwendete mathematische Methode, deren Ziel darin besteht, für ein gegebenes ganzzahliges Optimierungsproblem eine beste Lösung zu finden. Branch and Bound führt auf einen …   Deutsch Wikipedia

  • Branch and Cut — bzw. Verzweigung und Schnitt bezeichnet in der kombinatorischen Optimierung, einem Teilgebiet der diskreten Mathematik, ein Verfahren zur Lösung ganzzahliger linearer Optimierungsprobleme. Das Verfahren besteht aus der Kombination von… …   Deutsch Wikipedia

  • Branch-and-Cut — bzw. Verzweigung und Schnitt bezeichnet in der kombinatorischen Optimierung, einem Teilgebiet der diskreten Mathematik, ein Verfahren zur Lösung ganzzahliger linearer Optimierungsprobleme. Das Verfahren besteht aus der Kombination von… …   Deutsch Wikipedia

  • Numerische Verfahren — Die Liste numerischer Verfahren führt Verfahren der numerischen Mathematik nach Anwendungsgebieten auf. Inhaltsverzeichnis 1 Lineare Gleichungssysteme 2 Nichtlineare Gleichungssysteme 3 Numerische Integration 4 Approximation und Interpolation …   Deutsch Wikipedia

  • Simplex-Verfahren — Das Simplex Verfahren läuft von einer Ecke eines LP Polyeders zur nächsten, bis keine Verbesserung mehr möglich ist. Das Simplex Verfahren (auch Simplex Algorithmus) ist ein Optimierungsverfahren der Numerik zur Lösung linearer… …   Deutsch Wikipedia

  • Liste numerischer Verfahren — Die Liste numerischer Verfahren führt Verfahren der numerischen Mathematik nach Anwendungsgebieten auf. Inhaltsverzeichnis 1 Lineare Gleichungssysteme 2 Nichtlineare Gleichungssysteme 3 Numerische Integration …   Deutsch Wikipedia